MAX= float('inf')
#有向使用MAX 无法到达的点使用max
matrix = [
    [0,2,MAX,1,MAX,3,MAX,MAX],
    [MAX,0,6,MAX,5,MAX,MAX,MAX],
    [MAX,MAX,MAX,MAX,MAX,MAX,MAX,6],
    [MAX,10,MAX,0,MAX,MAX,2,MAX],
    [MAX,MAX,9,MAX,0,MAX,MAX,4],
    [MAX,MAX,MAX,5,MAX,0,4,MAX],
    [MAX,7,MAX,MAX,3,MAX,0,8],
    [MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX]
    ]


def dijkstra(matrix, start_node):
    
    #矩阵一维数组的长度，即节点的个数
    matrix_length = len(matrix)

    #访问过的节点数组
    used_node = [False] * matrix_length

    #最短路径距离数组
    distance = [MAX] * matrix_length

    #初始化，将起始节点的最短路径修改成0
    distance[start_node] = 0
    
    #将访问节点中未访问的个数作为循环值，其实也可以用个点长度代替。
    while used_node.count(False):
        min_value = float('inf')
        min_value_index = 999
        
        #在最短路径节点中找到最小值，已经访问过的不在参与循环。
        #得到最小值下标，每循环一次肯定有一个最小值
        for index in range(matrix_length):
            if not used_node[index] and distance[index] < min_value:
                min_value = distance[index]
                min_value_index = index
        
        #将访问节点数组对应的值修改成True，标志其已经访问过了
        used_node[min_value_index] = True

        #更新distance数组。
        #以B点为例：distance[x] 起始点达到B点的距离，
        #distance[min_value_index] + matrix[min_value_index][index] 是起始点经过某点达到B点的距离，比较两个值，取较小的那个。
        for index in range(matrix_length):
            distance[index] = min(distance[index], distance[min_value_index] + matrix[min_value_index][index])

    return distance




start_node = int(input('请输入起始节点:'))
result = dijkstra(matrix,start_node)
print('起始节点到其他点距离：%s' % result)